package com.lw.leetcode.tree.c;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 2246. 相邻字符不同的最长路径
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/18 19:58
 */
public class LongestPath {

    private int max = 0;

    public int longestPath(int[] parent, String s) {
        int length = parent.length;
        Node[] arr = new Node[length];
        char[] chars = s.toCharArray();
        arr[0] = new Node(chars[0]);
        for (int i = 1; i < length; i++) {
            if (arr[i] == null) {
                arr[i] = new Node(chars[i]);
            }
            int p = parent[i];
            if (arr[p] == null) {
                arr[p] = new Node(chars[p]);
            }
            arr[p].list.add(arr[i]);
        }
        find(arr[0]);
        return max;
    }

    private int find(Node node) {
        if (node == null) {
            return 0;
        }
        List<Node> list = node.list;
        if (list.isEmpty()) {
            max = Math.max(1, max);
            return 1;
        }
        int a = 0;
        int b = 0;
        for (Node no : list) {
            int c = find(no);
            if (no.c == node.c) {
                max = Math.max(c, max);
                continue;
            }
            if (c > a) {
                b = a;
                a = c;
            } else if (c > b) {
                b = c;
            }
            max = Math.max(a + b + 1, max);
        }
        return a + 1;
    }

    private static class Node {
        private char c;
        private List<Node> list = new ArrayList<>();
        public Node(char c) {
            this.c = c;
        }
    }

}
